﻿
class Solution{
    /**
     * 问题：求中心下标
     * 链接：https://leetcode.cn/problems/find-pivot-index/
     * 时间复杂度：O(N);
     * 空间复杂度：O(N);
     */
    public int pivotIndex(int[] nums) {
        int len = nums.length;

        int[] f = new int[len];
        int[] g = new int[len];

        //左区间前缀和
        f[0] = 0;
        for(int i = 1;i < len;i++)
            f[i] = f[i - 1] + nums[i - 1];

        //右区间前缀和
        g[len - 1] = 0;
        for(int j = len - 2;j >= 0;j--)
            g[j] = g[j + 1] + nums[j + 1];

        //遍历一遍数组即可完成比较
        for(int k = 0;k < len;k++){
            if(g[k] == f[k]) return k;
        }

        return -1;
    }


    /**
     * 问题：左右区间乘积是否相等
     * 链接：https://leetcode.cn/problems/product-of-array-except-self/
     * 时间复杂度：O(N);
     * 空间复杂度：O(N);
     */
    public static  int[] productExceptSelf(int[] nums) {
        int n = nums.length;

        int[] f = new int[n];
        int[] g = new int[n];

        //左区间
        f[0] = 1;
        for(int i = 1;i < n;i++)
            f[i] = f[i-1] * nums[i- 1];

        //右区间
        g[n-1] = 1;
        for(int j = n - 2;j >=0;j--)
            g[j] = g[j+1] * nums[j + 1];

        //遍历数组
        int[] answer = new int[n];
        for(int k = 0;k < n;k++)
            answer[k] = g[k] * f[k];

        return answer;
    }


}